import java.util.Arrays;

/**
 * @Description: 长度最小的子数组
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的
 * 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，
 * 并返回其长度。如果不存在符合条件的子数组，返回 0 。
 * @Date:Create in 9:20  2022/6/8
 */
public class minSubArrayLen0209 {

    public static void main(String[] args) {
        int target = 213;
        int[] nums = new int[]{12,28,83,4,25,26,25,2,25,25,25,12};
        System.out.println(minSubArrayLen4(target, nums));
    }

    //暴力解法 两个for
    public static int minSubArrayLen1(int target, int[] nums) {
        int size = nums.length, len = nums.length, right = 0, a = 0;

        for (int i = 0; i < len; i++) {
            a += nums[i];
        }
        if (a < target) return 0;

        for (int left = 0; left < len; left++) {
            int sum = 0;

            for (int j = left; j < len; j++) {
                sum += nums[j];
                if (sum >= target) {
                    right = j;
                    int temp = right - left + 1;
                    if (temp < size) {
                        size = temp;
                    }
                    break;
                }
            }
        }
        return size;
    }

    //暴力解法 三目运算符的使用
    public static int minSubArrayLen2(int target, int[] nums) {
        int result = nums.length;
        int sum = 0;
        int subLength = 0;
        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    subLength = j - i + 1;
                    result = (result < subLength) ? result : subLength;
//                    System.out.println(subLength);
                    break;
                }
            }
        }
        return result == nums.length ? 0 : result;
    }

    //滑动窗口
    public static int minSubArrayLen3(int target, int[] nums) {
        int result = nums.length+1;
        int sum = 0;// 滑动窗口数值之和
        int subLength = 0;// 滑动窗口的长度
        int i = 0;// 滑动窗口起始位置
        for(int j=0;j<nums.length;j++){
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while(sum >= target){
                subLength = j-i+1;
                result= result<subLength?result:subLength;
//                System.out.println(subLength);
                sum -= nums[i++];// 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        return result==nums.length+1?0:result;
    }

    public static int minSubArrayLen4(int target, int[] nums){
        int[] desc = new int[nums.length];
        Arrays.sort(nums);
        int toal = 0;
        int cout = 0;
        for(int i=nums.length-1;i>-1;i--){
            toal += nums[i];
            if(toal<target){
                cout++;
            }else{
                return cout+1;
            }
        }
        return 0;
    }
}
